9889. Произведение разностей

Задан массив целых чисел a₁, a₂, ..., a_n. Вычислите произведение

Если Вы не знакомы с краткой формой записи, то указанное произведение равно

|a₁ − a₂| * |a₁ − a₃| * ... * |a₁ − a_n| *

|a₂ − a₃| * |a₂ − a₄| * ... * |a₂ − a_n| * ... * |a_n-1 − a_n|

Другими словами, это произведение |a_i − a_j| для всех 1 ≤ i < j ≤ n.

Так как результат будет большим, вычислите его по модулю m.

Вход. Первая строка содержит два целых числа n (n ≤ 10⁵) и m (m ≤ 1000). Следующая строка содержит n целых чисел a₁, a₂, ..., a_n (0 ≤ a_i ≤ 10⁹).

Выход. Выведите значение произведения по модулю m.

Пример входа	Пример выхода
5 123 4 6 12 41 71	102

РЕШЕНИЕ

циклы

Анализ алгоритма

Если n > m, то обязательно найдутся такие a_i и a_j что |a_i – a_j| mod m = 0. Следовательно при n > m указанное произведение равно 0.

При n ≤ m вычисляем произведение при помощи двойного цикла.

Реализация алгоритма

Входную последовательность храним в массиве а.

long long a[200000];

Читаем входные данные.

scanf("%d %d", &n, &m);

for (i = 0; i < n; i++)

scanf("%lld", &a[i]);

В переменной res вычисляем ответ.

res = 1;

При n > m искомое произведение равно 0.

if (n > m) res = 0;

else

{

Иначе вычисляем произведение при помощи двойного цикла.

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

res = (res * abs(a[j] - a[i])) % m;

}

Выводим ответ.

printf("%lld\n", res);